Networks require a protocol for routing data from an originating node to a destination node, since in order to reach its destination the data must traverse an oftentimes vast, intricately interconnected group of intermediate nodes. A link-state protocol is one type of routing protocol for calculating a shortest available route between an originating node and a destination node. Typically used in a packet-switched network, a link-state protocol gives to each node the ability to calculate the best route to a destination for a packet it has received. In order for every node to do such routing, each node must create a routing table showing the shortest (or least costly) path from itself to every other possible destination in the network. In significantly large networks, the scope of the routing table for a node may cover the connectivity of only a sub-area of nodes in the network. In order to determine a routing table, the node must receive information indicating the overall network topology, that is, information indicating how every node is linked in the network.
One type of link-state protocols is Open Shortest Path First (OSPF). The OSPF standard is described in Moy, J., “OSPF Version 2,” IETF RFC 2328, April, 1998, which is hereby incorporated by reference. Other documents describing the OSPF standard include Coltun R., D. Ferguson, J. Moy, “OSPF for IPV6,” IETF RFC 2740, December, 1999; and Katz D., K. Kompella, D. Yeung, “Traffic engineering Extensions to OSPF Version 2,” IETF RFC 3630, September 2003, both of which as well are hereby incorporated by reference. As explained above, every node in an OSPF network determines a routing table, but before it can do so it must receive from every other node in the network a link state advertisement (LSA). In the OSPF protocol, an LSA is a type of link state message that contains all the link information for the node that generated the LSA. The LSA of every node is flooded throughout the entire network to ensure that every node has sufficient information to generate its own routing table.
In the header of every type of LSA message is an LS age field. Currently in all versions of the OSPF protocol the LS age field of every type of LSA is set to 0 by the originating node (typically embodied as a router). The LS age (in seconds) is increased, usually by one per hop, as it is flooded and also aged according to standard clock time while it is stored in the database. LSAs are refreshed by the originating node as soon as it reaches the value LSRefreshTime (default 1800 seconds). It is possible for the refresh instants of a vast number of LSAs to be synchronized, thereby causing an LSA storm. During an LSA storm, some nodes, particularly ones with less powerful processors, cannot keep up with the workload. This may result in many retransmissions, loss of adjacency, and eventually loss of customer traffic.